package jm.data.structure.union_find;

/**
 * @Description rank优化 —— 路径分裂
 * @date 2022/5/9 21:11
 */
public class QuickUnionPS extends AbstractUnionFind{
    // 记录 '树' 的高度
    private int[] ranks;

    public QuickUnionPS(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        // 将当前 ‘树’ 的高度默认为 1
        for (int i = 0; i < ranks.length; i++) {
            ranks[i] = 1;
        }
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 让元素的父节点改为祖父节点
        while (v != parents[v]){
            int p = parents[v];
            parents[v] = parents[parents[v]];
            v = p;
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        // 将矮的树嫁接到高的树上
        if (ranks[p1] < ranks[p2]){
            parents[p1] = p2;
        }else if (ranks[p1] > ranks[p2]){
            parents[p2] = p1;
        }else {
            parents[p1] = p2;
            ranks[p2] += 1;
        }
    }
}
